package com.aqie.medium.dynamicProgram;

import java.util.Arrays;
import java.util.List;

/**
 * 96 1-n组成的二叉搜索树有多少 TODO
 */
public class NumTrees {
    /**
     * 1, DP x < y < z < k, 则任意x y z k组合的二叉搜索树总数相同 26ms
     * DP 使用list
     * @param n
     * @return
     */
    public static int numTrees(int n) {
        if (n < 0) return 0;
        // list set / get 及 初始化， 及 没有 add() 方法
        List<Integer> list = Arrays.asList(new Integer[n + 1]);
        for (int i = 0; i<list.size(); i++) {
            list.set(i,0);
        }

        list.set(0,1);
        list.set(1,1);
        for (int i= 2; i <= n; ++i){
            for (int j = 1; j <= i; ++j){
                System.out.println((j-1) + " " + (i-j) + " " + i);
                list.set(i, list.get(i) + list.get(j - 1) * list.get(i - j));
            }
        }
        // list 转 int  list.stream().mapToInt(Integer::valueOf).toArray();
        System.out.println(list);
        return list.get(n);
    }

    /**
     * 2, DP 使用数组 O(N^2) - O(N) 0ms
     * @param n
     * @return
     */
    public int numTrees2(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }

    /**
     * 3, 数学演绎法 O(N) - O(1) 0ms
     * @param n
     * @return
     */
    public int numTrees3(int n) {
        // Note: we should use long here instead of int, otherwise overflow
        long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;
    }



    public static void main(String[] args) {
        numTrees(3);
        // 数组默认初始化 0
        int[] A = new int[4];
        System.out.println(A[3]);
    }
}
